// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用一次。
// 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
// 思路，回溯 + 去重
// candidates可能有重复的元素，但是最终的结果不能有重复的组合，就是说candidates中的元素只能用一次
// 递归问题可以看做是一个树，同一树层不能重复，同一树枝可以重复，因为candidates可能有重复的元素，但是结果中的组合不能重复，所以，遍历的过程中重复的元素需要continue跳过

function combinationSum2(candidates, target) {
    let result = []
    let path = []
    function backtracking(startIndex, sum) {
        if (sum === target) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break
            }
            // 要对同一树层使用过的元素进行跳过
            if (i > startIndex && candidates[i] === candidates[i-1]) {
                continue
            }
            path.push(candidates[i])
            backtracking(i + 1, sum + candidates[i])
            path.pop()
        }
    }
    candidates.sort((x, y) => x - y)
    backtracking(0, 0)
    return result
}

let candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
console.log(combinationSum2(candidates, target))